//
// Created by liushuai on 2020/5/6.
//
#include "TreeOperator.h"
bool isSymmetric(TreeNode* root1,TreeNode* root2){
    if(!root1&&!root2)//两个节点都为空
        return true;
    //两个节点有一个不为空都为空二叉树
    if(!root1&&root2)
        return false;
    if(root1&&!root2)
        return false;
    // 两个节点都不为空，但是节点值不同
    if(root1&&root2&&root1->val!=root2->val)
        return false;
    // 判断节点相同的树左右子树
    else{
        return isSymmetric(root1->left,root2->right)&&isSymmetric(root1->right,root2->left);
    }
}
bool isSymmetric(TreeNode* root){
    if(!root)//空树为对称二叉树
        return true;
    else
        return isSymmetric(root,root);
}

bool isValidBST(TreeNode* root,long min,long max){
    // 空树为BST
    if(!root)
        return true;
    // 不满足BST数条件
    if(root->val<=min||root->val>=max){
        return false;
    }
    // 满足BST条件，将当前节点和上级节点比较
    return isValidBST(root->left,min,root->val) &&isValidBST(root->right,root->val,max);
}
bool isValidBST(TreeNode* root){
    return isValidBST(root,LONG_MIN,LONG_MAX);
}

TreeNode* sortedArrayToBST(std::vector<int>& nums) {
    return sortedArrayToBST(nums,0,nums.size()-1);
}
TreeNode* sortedArrayToBST(std::vector<int>& nums,int l,int r){
    if(r<l)
        return nullptr;
    int mid = l/2+(r-l)/2;
    TreeNode* root= new TreeNode(nums[mid]);
    root->left = sortedArrayToBST(nums,l,mid-1);
    root->right = sortedArrayToBST(nums,mid+1,r);
    return root;
}
